﻿#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

////打印链表
//void SLprint(SL* phead)
//{
//	SL* pcur = phead;
//	while (pcur)
//	{
//		printf("%d->", pcur->val);
//		pcur = pcur->next;
//	}
//	printf("NULL\n");
//}
// 创建节点
SL* buynode(SLTDataType x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

//尾插
void SLPushBack(SL** pphead, SLTDataType x)
{
	assert(pphead);
	SL* newnode = buynode(x);
	if (*pphead == NULL) //若链表为空，新节点为有效头节点
	{
		*pphead = newnode;
	}
	else // 若不为空链表，则尾插
	{
		SL* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}
//尾删
void SLPopBack(SL** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		printf("已经是空链表了，无需删除\n");
		return;
	}
	else if ((*pphead)->next == NULL)//若只有一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else // 有多个节点
	{
		// 找到尾节点和尾节点的前一个节点
		SL* prev, * pcur;
		prev = pcur = *pphead;
		while (pcur->next)
		{
			prev = pcur;
			pcur = pcur->next;
		}
		prev->next = NULL;
		free(pcur);
		pcur = NULL;
	}
}
//头插
void SLPushFront(SL** pphead, SLTDataType x)
{
	assert(pphead);
	SL* newnode = buynode(x);
	// 创建新节点，新节点连接原链表
	// 新节点作新有效头节点
	newnode->next = *pphead;
	*pphead = newnode;
}
//头删
void SLTPopFront(SL** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		printf("已经是空链表了，无需删除\n");
		return;
	}
	//有效头节点的下一个节点作新有效节点
	SL* pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}
//// 查找
//SL* SLFind(SL* phead, char* name)
//{
//	SL* pcur = phead;
//	// 遍历链表
//	while (pcur)
//	{
//		// 若该节点的值是要找的值，返回该节点的地址
//		if (pcur->val == x)
//		{
//			return pcur;
//		}
//		pcur = pcur->next;
//	}
//	// 遍历链表未找到，返回NULL
//	return NULL;
//}
//在指定位置之前插入数据
void SLInsert(SL** pphead, SL* pop, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pop);
	// 若在头节点之前插入，就是头插
	if (pop == *pphead)
	{
		SLPushFront(pphead, x);
	}
	else
	{
		//遍历找到该节点的上一个节点
		SL* prev = *pphead;
		SL* newnode = buynode(x);
		while (prev->next != pop)
		{
			prev = prev->next;
		}
		// 插在中间
		newnode->next = pop;
		prev->next = newnode;
	}
}
//删除pos节点
void SLErase(SL** pphead, SL* pop)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		printf("已经是空链表了，无需删除\n");
		return;
	}
	else if (*pphead == pop) //若删除的是有效头节点
	{
		SLTPopFront(pphead); //头删
	}
	else
	{
		// 找到该节点的前一个节点
		SL* pcur = *pphead;
		while (pcur->next != pop)
		{
			pcur = pcur->next;
		}
		// 前一个节点连接后一个节点，删除中间节点
		pcur->next = pop->next;
		free(pop);
		pop = NULL;
	}
}
//在指定位置之后插入数据
void SLInsertAfter(SL* pop, SLTDataType x)
{
	assert(pop);
	// 在该节点和下一个节点中间插入
	SL* newnode = buynode(x);
	newnode->next = pop->next;
	pop->next = newnode;
}
//删除pos之后的节点
void SLEraseAfter(SL* pop)
{
	assert(pop);
	if (pop->next == NULL)
	{
		printf("该节点之后已经为空，无需删除\n");
		return;
	}
	SL* prev = pop->next;
	pop->next = prev->next;
	free(prev);
	prev = NULL;
}
//销毁链表
void SListDesTroy(SL** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		printf("该链表为空，无需销毁\n");
		return;
	}
	SL* pcur = *pphead;
	while (pcur)
	{
		SL* ret = pcur->next;
		free(pcur);
		pcur = ret;
	}
	*pphead = NULL;
}